package code;

/**
 * 位运算
 * 实现加减乘除等功能
 *
 * @author lixun
 * @date 2022/9/30-11:23
 * @since [v1.0]
 */
public class Operation {

    /**
     * 加
     * @author lixun
     * @date 2022/9/30 13:26
     */
    public int addition(int a, int b) {
        // b为0返回a
        while (b != 0) {
            // a异或b 不进位的数
            int i = a ^ b;
            // a位与b左移一位 进位的数
            b = (a & b) << 1;
            a = i;
        }
        return a;
    }

    /**
     * 加 递归实现
     * @author lixun
     * @date 2023/8/31 15:01
     */
    public int additionRecursion(int a, int b) {
        return b == 0 ? a : additionRecursion(a ^ b, (a & b) << 1);
    }

    /**
     * 减
     * @author lixun
     * @date 2022/9/30 13:43
     */
    public int subtraction(int a, int b) {
        // 减去一个数位加上一个数的相反数
        return addition(a, ~b + 1);
    }

    /**
     * 乘
     * @author lixun
     * @date 2022/9/30 14:25
     */
    public int multiplication(int a, int b) {
        int n = 0;
        // 二进制低位向高位遍历，a*b的值即为a与b二进制的每一位的相乘的和
        for (int i = 0; i < 32; i++) {
            // b二进制的第i位不为0时累加a右移i位
            if (((1 << i) & b) != 0) {
                n += a << i;
            }
        }
        return n;
    }

    /**
     * 除
     * @author lixun
     * @date 2022/9/30 18:21
     */
    public int division(int a, int b) {
        if (a == 0) {
            throw new ArithmeticException("/by zero");
        }
        if (b == 0) {
            return 0;
        }
        // 结果正负
        boolean sign = (a < 0 || b > 0) && (a > 0 || b < 0);
        long al = Math.abs((long) a), bl = Math.abs((long) b);
        int n = 0;
        // 由二进制高位向低位遍历，与乘类似但相反
        for (int i = 31; i >= 0; i--) {
            long bb = bl << i;
            // b的二进制右移i位，小于a,即为a>b*(1<<i)
            // a减去此值，结果n加上1<<i,循环直到a<b，此时n位a/b的绝对值
            if (bb <= al) {
                n += 1 << i;
                al -= bb;
            }
        }
        return sign ? n : -n;
    }

    /**
     * 负，取反
     * @author lixun
     * @date 2022/9/30 13:50
     */
    public int negative(int a) {
        return addition(~a, 1);
    }

    /**
     * 二进制最高位
     * @author lixun
     * @date 2022/10/8 17:24
     */
    public int high(int a) {
        if (a == Integer.MIN_VALUE) {
            return 31;
        }
        a = a >= 0 ? a : -a;
        a |= a >> 1;
        a |= a >> 2;
        a |= a >> 4;
        a |= a >> 8;
        a |= a >> 16;
        a = a + 1 >>> 1;
        for (int i = 0; i < 31; i++) {
            if (((1 << i) & a) != 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 二进制最低位
     * @author lixun
     * @date 2022/10/8 17:24
     */
    public int low(int a) {
        a &= -a;
        for (int i = 0; i < 31; i++) {
            if (((1 << i) & a) != 0) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 展示二进制
     * @author lixun
     * @date 2022/10/18 17:20
     */
    public static void showBinary(int n) {
        for (int r = 31; r >= 0; r--) {
            System.out.print((n >> r) & 1);
        }
        System.out.println();
    }

    public static void showBinary(long n) {
        for (int r = 63; r >= 0; r--) {
            System.out.print((n >> r) & 1);
        }
        System.out.println();
    }

    public static void showBinaryFloat(float f) {
        int n = (int) f;
        for (int r = 31; r >= 0; r--) {
            System.out.print((n >> r) & 1);
        }
        System.out.println();
    }
    /**
     * 最大公约数
     * greatest common divisor(gcd)
     * @author lixun
     * @date 2022/10/19 10:40
     */
    public int gcd(int a, int b) {
        while (b != 0) {
            int y = a % b;
            a = b;
            b = y;
        }
        return a;
    }

    public static void main(String[] args) {
        Operation o = new Operation();
        o.showBinary(65535);
        o.showBinary(65536);
        System.out.println(o.addition(-2,6));
        System.out.println(Integer.MAX_VALUE + Integer.MAX_VALUE);
        System.out.println(o.negative(Integer.MAX_VALUE));
        System.out.println(o.subtraction(-3,5));
        System.out.println(o.addition(Integer.MIN_VALUE,Integer.MIN_VALUE));
        System.out.println(Integer.MAX_VALUE * 4);
        System.out.println(o.multiplication(-2,-4));
        System.out.println(o.multiplication(-1,-7));
        System.out.println((-6 << 24) * -28);
        System.out.println(o.multiplication(-6 << 24,-28));
        System.out.println();
        System.out.println(o.multiplication(-200000,700000));
        System.out.println(-200000 * 700000);
        System.out.println(2 ^ -4);
        System.out.println(o.division(-666,2));
        System.out.println(o.division(1 << 31,1 << 30));
        System.out.println(o.multiplication(Integer.MIN_VALUE,2));
        System.out.println(Integer.MIN_VALUE * 2);
        System.out.println(o.multiplication(-666,10));
        System.out.println(o.division(18648,666));
        System.out.println(o.high(1024));
        System.out.println(o.low(1024));
        System.out.println(o.division(1000,3));
        System.out.println(1000 / 3);
        System.out.println(o.division(1 << 30, 1 << 20));
        System.out.println((1 << 30) / (1 << 20));
        System.out.println(o.division(99012489,3));
        System.out.println(99012489 / 3);
        System.out.println(o.division(1 << 31, 1 << 31));
        System.out.println(o.low(12));
    }
}
